#define _CRT_SECURE_NO_WARNINGS 1

class Solution
{
public:
	void sortColors(vector<int>& nums)
	{
		int n = nums.size();
		int left = -1, right = n, i = 0;
		while (i < right)
		{
			if (nums[i] == 0) swap(nums[++left], nums[i++]);
			else if (nums[i] == 1) i++;
			else swap(nums[--right], nums[i]);
		}
	}
};